package com.tucc.hello.leetcode.no801_1200.no993;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode.no801_1200.no993
 * @date 2021/5/17
 */
public class Solution {

    public static void main(String[] args) {
        /**
         * [1,2,3,null,4,null,5]
         * 5
         * 4
         */
        TreeNode root = new TreeNode();
        root.val = 1;
        root.left = new TreeNode();
        root.left.val = 2;
        root.left.right = new TreeNode();
        root.left.right.val = 4;
        root.right = new TreeNode();
        root.right.val = 3;
        root.right.right = new TreeNode();
        root.right.right.val = 5;
        System.out.println(new Solution().isCousins(root, 5, 4));
    }

    /**
     * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
     * <p>
     * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
     * <p>
     * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
     * <p>
     * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
     *
     * @param root
     * @param x
     * @param y
     * @return
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        List<Integer> targetList = new ArrayList<>();
        targetList.add(x);
        targetList.add(y);
        Map<Integer, List<Integer>> result = new HashMap<>();
        find(root, targetList, 1, result);
        List<Integer> resultX = result.get(x);
        List<Integer> resultY = result.get(y);
        if (resultX != null && resultY != null) {
            return !resultX.get(0).equals(resultY.get(0))
                    && resultX.get(1).equals(resultY.get(1));
        }
        return false;
    }

    public void find(TreeNode node, List<Integer> targetList, int curDeep,
                     Map<Integer, List<Integer>> result) {
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        if (targetList.isEmpty()) {
            return;
        }
        Iterator<Integer> iterator = targetList.iterator();
        while (iterator.hasNext()) {
            Integer target = iterator.next();
            if ((node.left != null && node.left.val == target)
                    || (node.right != null && node.right.val == target)) {
                iterator.remove();
                List<Integer> list = new ArrayList<>();
                list.add(node.val);
                list.add(curDeep);
                result.put(target, list);
            }
        }
        if (targetList.isEmpty()) {
            return;
        }
        find(node.left, targetList, curDeep + 1, result);
        find(node.right, targetList, curDeep + 1, result);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
